package com.leetcode.partition9;

import java.util.Stack;

/**
 * @author `RKC`
 * @date 2021/10/21 10:15
 */
public class LC844比较含退格的字符串 {

    public static boolean backspaceCompare(String s, String t) {
//        return stackSolution(s, t);
        return doublePointer(s, t);
    }

    public static void main(String[] args) {
        String s = "abaa##c", t = "aaa#a#c";
        System.out.println(backspaceCompare(s, t));
    }

    private static boolean doublePointer(String s, String t) {
        int i = s.length() - 1, j = t.length() - 1;
        int skipS = 0, skipT = 0;
        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (s.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (t.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0 && s.charAt(i) != t.charAt(j)) {
                return false;
            }
            i--;
            j--;
        }
        System.out.println(i);
        System.out.println(j);
        return i == j;
    }

    private static boolean stackSolution(String s, String t) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != '#') stack.push(s.charAt(i));
            else if (!stack.isEmpty()) stack.pop();
        }
        StringBuilder sbs = new StringBuilder();
        while (!stack.isEmpty()) {
            sbs.append(stack.pop());
        }
        for (int j = 0; j < t.length(); j++) {
            if (t.charAt(j) != '#') stack.push(t.charAt(j));
            else if (!stack.isEmpty()) stack.pop();
        }
        StringBuilder sbt = new StringBuilder();
        while (!stack.isEmpty()) {
            sbt.append(stack.pop());
        }
        return sbs.toString().equals(sbt.toString());
    }
}
